\section{Ejercicio 1}

\subsection{Enunciado}

Dado un vector $v$ de enteros, se define meseta como un segmento de posiciones consecutivas con el mismo valor. Sean
dos arreglos $A$ e $B$ no vac\'ios cada uno ordenado en Forma no 
decreciente. Hallar la longitud de la meseta m\'as extensa
aque surja de combinar ambos vectores en uno resultante, tambi\'en 
ordenado. Resolver el problema en $O(long(A) + long(B))$.

\textbf{Entrada: } \texttt{Tp1Ej1.in}

El archivo contiene varias instancias, cada una consta de dos l\'ineas, una para cada vector con los enteros separados por
un espacio en blanco.

\textbf{Salida: } \texttt{Tp1Ej1.out}

Para cada instancia de entrada, se debe indicar una l\'inea con la longitud de la meseta encontrada.

\subsection{Introducci\'on}

Nuestro algoritmo resuelve el ejercicio utilizando la t\'ecnica de combinaci\'on
o \textit{merge} de arreglos ordenados, y luego emplea un simple algoritmo
goloso para calcular las meseta m\'as extensa en una sola pasada, 
obteniendose la complejidad temporal pedida: $O(n+m)$ con $n,m$ las 
longitudes de los arreglos, y con $O(n+m)$ memoria adicional, para 
simplificar la implementaci\'on. 

\subsection{Desarrollo}

\subsubsection{Notaci\'on}

A lo largo de la explicaci\'on de nuestro algoritmo (y posiblemente en otras partes del 
trabajo pr\'actico tambi\'en), emplearemos notaci\'on
de listas. En particular utilizaremos la siguiente notaci\'on: Si $A$ y $B$
son listas:

\begin{itemize}
	\item $long(A)$ es la longitud de la lista $A$
	\item $head(A)$ consiste en el primer elemento de $A$.
	\item $tail(A)$ consiste en la lista de todos los elementos de $A$ menos el primero.
	\item $last(A)$ consiste en el \'ultimo elemento de $A$.
	\item $empty(A)$ es un valor booleano correspondiente a si la lista es o no vac\'ia.
	\item $A \cup B$ consiste en la concatenaci\'on de las listas $A$ y $B$
	\item $A \bullet e$ para denotar la concatenaci\'on del elemento $e$ al final de la lista $A$.
\end{itemize}

\subsubsection{Explicaci\'on del Algoritmo}

En primera instancia, el algoritmo combina los dos arreglos ordenados, 
que denominaremos $A$ y $B$, en un nuevo arreglo ordenado $C$ de 
longitud $n+m$, donde la longitud de $A$ es $n$ y la de $B$ es $m$. 

Para hacer esto se emplea el conocido m\'etodo de combinaci\'on de 
arreglos o \textit{merge}, parte fundamental del algoritmo 
\textit{mergesort}, que nos permite resolver este paso en $O(n+m)$. 
Este pseudoc\'odigo se detalla a continuaci\'on, utiliz\'andose para 
mayor claridad de la explicaci\'on la notaci\'on de listas.

\begin{algorithm}[!h] 
	\caption{Pseudoc\'odigo para combinar dos arreglos ordenados $A$ y $B$ en un 
	arreglo ordenado $C$.}
	\label{algo::merge}
	\begin{algorithmic}
		\While{$\neg empty(A) \vee \neg empty(B)$}
			\If{$empty(A)$}
				\State $elem \gets head(B)$
				\State $B \gets tail(B)$
				\State
			\ElsIf{$empty(B)$}
				\State $elem \gets head(A)$
				\State $A \gets tail(A)$
			\ElsIf{$head(A) > head(B)$}
				\State $elem \gets head(B)$
				\State $B \gets tail(B)$
			\Else
				\State $elem \gets head(A)$
				\State $A \gets tail(A)$
			\EndIf
			\State $C \gets C \bullet elem$  
		\EndWhile
		
		\State \Return C
	\end{algorithmic}
\end{algorithm}

La correctitud de este algoritmo puede demostrarse mediante teorema del
invariante. Para ello emplearemos la siguiente funci\'on variante e 
invariante del ciclo

\begin{itemize}
	\item \textbf{Funcion Variante:} $long(A) + long(B)$.
	\item \textbf{Invariante del ciclo:} En la $k$-\'esima iteraci\'on, 
	$C$ es la lista ordenada de los $k-1$ elementos m\'as peque\~nos de
	$A \cup B$ (considerando multiplicidad), y los elementos 
	restantes de $B$ son mayores que los elementos ya vistos de $A$, y 
	similar para $A$ y $B$.
\end{itemize}

Y entonces demostraremos el siguiente

\begin{lemma}
	El algoritmo de combinaci\'on de arreglos devuelve el arreglo 
	ordenado $C$ cuyos elementos son los elementos de $A \cup B$ para
	los arreglos $A$ y $B$ pasados por par\'ametro.
\end{lemma}

\begin{proof}
	Demostramos cada uno de los siguientes items, que corresponden al 
	teorema del invariante, por separado.
	
	\begin{itemize}
		\item \textbf{El invariante se cumple antes de entrar al 
		ciclo:} Esto se cumple por vac\'io, ya que al no haberse 
		ejecutado ninguna iteraci\'on del ciclo, el arreglo $C$ no 
		contiene elementos. De la misma manera, al no haberse 
		ejecutado ninguna iteraci\'on, $A$ y $B$ son iguales a los 
		arreglos originales, y todos los elementos restantes de $A$ son 
		mayores que los elementos vistos de $B$ y todos los elementos restantes de $B$ 
		son mayores que los elementos vistos de $A$ (nuevamente por 
		vac\'io).
		\item \textbf{El invariante se mantiene entre iteraciones: }
		Supongamos que vale el invariante en una iteraci\'on $k$ dada.
		Sean $A_k$ y $B_k$ los arreglos $A$ y $B$ en ese momento, y 
		sea $C_k$ el arreglo de combinaci\'on en ese momento. Sean 
		tambi\'en $A_k'$ y $B_k'$ los subarreglos sufijos de $A$ y $B$ 
		que ya hemos examinado (y cuyos elementos ya metimos en $C$). 
		
		El algoritmo procede entonces obteniendo el pr\'oximo elemento a agregar, 
		$elem$, como el m\'inimo entre $head(A)$ y $head(B)$, con la 
		consideraci\'on de que si una de los dos arreglos esta vac\'io 
		se tome el elemento siguiente del otro (lo cual podemos hacer 
		porque la guarda del ciclo nos asegura de que alguno de los 
		dos arreglos restantes $A_k$ o $B_k$ es no vac\'io). No 
		consideraremos estos casos puesto que las proposiciones 
		enunciadas en el invariante valen por vac\'io (por ejemplo, si 
		$A_k$ no tiene elementos restantes entonces por vac\'io todos 
		sus elementos cumplen que son mayores a los ya vistos, y que 
		todos sus elementos son menores al $elem$ extra\'ido).
		
		\begin{itemize}
			\item $(\forall e \in A_k) elem \leq e.$: Trivial de la 
			definici\'on de m\'inimo y de que $A_k$ es tambi\'en un 
			arreglo ordenado.
			\item $(\forall e \in B_k) elem \leq e.$: An\'alogo al 
			caso para $A_k$.
			\item $(\forall e \in A_k') elem \geq e$. Tenemos dos 
			casos. El caso en que $elem = head(A_k)$ es trivial ya que 
			por ser $A$ un arreglo ordenado y $A_k'$ y $A_k$ dos 
			subarreglos continuos disjuntos de $A$ donde $A_k$ son 
			todos los elementos que aparecen despu\'es de los de $A_k'$, 
			$elem = head(A_k) \geq last(A_k') \geq e$, $(\forall e \in 
			A_k')$. En cambio, sea $elem = head(B_k)$. Por la segunda 
			parte del invariante, todos los elementos de $B_k$ son 
			mayores que los elementos de $A_k'$, por lo tanto en 
			particular $head(B_k) = elem$ es mayor que todo elemento 
			de $A_k'$ como queriamos demostrar.
			\item $(\forall e \in B_k') elem \geq e$ An\'alogo al 
			caso de $A_k'$.
		\end{itemize} 
		
		F\'acilmente podemos ver entonces que $elem$ corresponde al 
		$k+1$-\'esimo elemento m\'as chico de $A \cup B$. Tambi\'en 
		podemos ver que dado que $A_k$ y $B_k$ estan ordenados y $elem 
		\leq head(A_k) \leq e, (\forall e \in A_k)$ y $elem \leq 
		head(B_k) \leq e, (\forall e \in B_k)$ por la condici\'on de 
		m\'inimo, entonces quitar el 
		elemento $elem$ del arreglo que corresponda mantiene el 
		invariante de que todos los elementos restantes de $A$ y $B$ 
		son mayores que los elementos ya vistos de $A$ y $B$, porque 
		quitamos el m\'inimo de los elementos restantes de $A$ y $B$ 
		(ya que por la condici\'on de .
		
		Por lo tanto, el invariante se cumple entre iteraciones del 
		ciclo, ya que al finalizar a $C$, contiene los $k$ elementos 
		m\'as chicos de $A \cup B$, se le agrega al final el $k+1$-\'esimo elemento de $A 
		\cup B$, y al quitarse el m\'inimo elemento a alguna de las 
		dos listas $A_k$ o $B_k$, los restantes elementos son mayores 
		que todos los vistos.
		\item \textbf{Si la funci\'on variante vale cero el ciclo 
		termina}: Esto es obvio del hecho de que $\neg( \neg empty(A) \vee 
		\neg empty(B) ) \equiv \neg \neg (long(A) = 0 \wedge long(B)) 
		\equiv (long(A) = 0 \wedge long(B) = 0) \equiv long(A) + 
		long(B) = 0$ pues las longitudes son siempre n\'umeros no 
		negativos.
		\item \textbf{La funci\'on variante disminuye en uno en cada 
		iteraci\'on}: Esto resulta obvio del hecho de que en cada 
		iteraci\'on uno y solo uno de los dos arreglos reduce su longitud en 
		1, ya que se quita el primer elemento de alguna de ellas. Por 
		lo tanto $long(A_{k+1}) + long(B_{k+1}) = long(A_k) + long(B_k) - 
		1$ donde por $k$ nos referimos al n\'umero de iteraci\'on 
		actual.
	\end{itemize}
	
Teniendo esta inFormaci\'on como base, es obvio que si $n$ y $m$ 
eran las longitudes de los arreglos originales, el ciclo itera 
$n+m$ veces. Por lo tanto, al finalizar la $n+m$-\'esima 
iteraci\'on, $C$ contiene la lista ordenada de los $n+m$ elementos 
m\'as chicos de $A \cup B$. Pero como $A \cup B$ contiene 
exactamente $n+m$ elementos, tenemos entonces que $C$ es la lista
ordenada de todos los elementos de $A \cup B$, como quer\'iamos 
demostrar. 

Esto concluye la demostraci\'on de la correctitud del 
algoritmo de combinaci\'on de arreglos. \qed
\end{proof}

Posteriormente, procedemos a obtener la meseta m\'axima del arreglo 
obtenido, mediante el siguiente algoritmo (ver algoritmo~\ref{algo::meseta}).

\begin{algorithm}[!h] 
	\caption{Pseudoc\'odigo del algoritmo para obtener la meseta m\'axima de un 
	arreglo $A$.}
	\label{algo::meseta}
	\begin{algorithmic}
		\State $n \gets long(A)$
		\State \Comment{Se asume que $n > 0$}
		\Statex

		\State $mesetaMaxima \gets 0$
		\State $mesetaActual \gets 0$
		\State $valorActual \gets A[0]$
		\Statex

		\For{$i = 0 \to n-1$}
			\If{$A[i] = valorActual$}
				\State $mesetaActual \gets mesetaActual+1$
			\Else
				\State $mesetaMaxima \gets \max \{ mesetaActual, 
				mesetaMaxima \}$
				\State $mesetaActual \gets 1$
				\State $valorActual \gets A[i]$
			\EndIf
		\EndFor
		\Statex

		\State $mesetaMaxima \gets \max \{ mesetaActual, mesetaMaxima \}$
		\State \Return mesetaMaxima
	\end{algorithmic}
\end{algorithm}

El algoritmo lo que hace es recorrer los elementos del arreglo 
manteniendo la cantidad de elementos de la meseta actual, y el valor 
correspondiente a los elementos de le meseta actual. Si el valor del 
elemento que estamos mirando actualmente es igual al de la meseta 
actual, entonces podemos extender la longitud de la meseta actual en 1 
(para lo cual incrementamos el contador $mesetaActual$). Si no lo es, 
entonces la meseta actual ya termin\'o, por ser una meseta de $A$ un subarreglo  
continuo de elementos de $A$, y entonces actualizamos el valor de 
la meseta m\'axima (esto evita tener que guardar el valor de todas las 
mesetas para posteriormente obtener el valor m\'aximo), e iniciamos 
una nueva meseta cuyo valor corresponde a este nuevo elemento de $A$ 
que encontramos y cuya longitud es uno por contener un solo elemento.

Finalmente el algoritmo necesita actualizar una vez m\'as el valor de 
$mesetaMaxima$ porque el valor de la \'ultima meseta (es decir, de la 
meseta que contiene al \'indice $n-1$), que esta en $mesetaActual$,
no es comparado en el cuerpo del ciclo.

N\'otese que por la definici\'on de meseta como subarreglo contiguo de elementos
con el mismo valor, no es necesario pedir que el arreglo $A$ este \'ordenado para
que el algoritmo sea correcta, ya que este revisa por secciones contiguas.

La correctitud de este algoritmo surge nuevamente del teorema del 
invariante.

A partir de ahora, por $meseta(j)$ nos referimos a la longitud de la meseta m\'as 
larga que contiene al \'indice $j$. N\'otese que dado que consideramos la 
meseta m\'as larga, $meseta(j)$ tiene un \'unico valor bien definido, 
por ser el m\'aximo de un conjunto (el de las mesetas que contienen el 
\'indice $j$) no vac\'io (ya que para todo $j$, el conjunto que 
contiene solamente a $j$ es una meseta continua que contiene a esta) y finito
(puesto que como mucho todo el array puede ser la meseta m\'axima).

\begin{itemize}
	\item \textbf{Funcion Variante:} $n-1-i$.
	\item \textbf{Invariante del ciclo:} En la $i$-\'esima iteraci\'on 
	$valorActual_i = A[i]$, $mesetaActual_i = 
	i+1-l_i$ donde $l_i = \min \{ j | 0 \leq j < n, (\forall k, j \leq k \leq i) A[k] = A[i] 
	\}$, y $mesetaMaxima_i = \max \{ h_j - l_j + 1 | (\forall j) 1 \leq j < l_i \}$ si $i > 0$, $0$ si $i = 0$,
	y donde $h_i = \max \{ j | 0 \leq j < n, (\forall k, i \leq k \leq j) A[k] = A[i] \}$.
\end{itemize}

Donde la notaci\'on de sub\'indices tiene el prop\'osito de denotar el valor particular para la iteraci\'on que se esta llevando
acabo.

Intuitivamente lo que queremos decir es que $mesetaActual$ tiene la cantidad de elementos cuyo valor
es el de la meseta que estamos mirando actualmente, $mesetaMaxima$ tiene la cantidad de elementos de la
mesetas m\'aximas vistas hasta ahora, y $valorActual$ es el valor del elemento del comienzo de la meseta que
estamos mirando ahora. Lo que queremos es ver que esto es un invariante del ciclo, lo cual implicar\'ia que
la variable $mesetaMaxima$ contiene el m\'aximo de todas las mesetas menos la \'ultima, lo cual arreglamos
actualizando $mesetaMaxima$ si es necesario antes de devolver su valor.

Para definir formalmente las nociones de $mesetaMaxima$ y $mesetaActual$, utilizamos los valores $l_i$ y
$h_i$. $l_i$ corresponde al inicio de la meseta m\'axima que contiene al \'indice $i$, y $h_i$ corresponde
al \'ultimo elemento de la meseta m\'axima que contiene al \'indice $i$. En particular entonces, vemos que
$h_i - l_i + 1$ corresponde a la cantidad de elementos de la meseta m\'axima que contiene a $i$. Es decir
tenemos la siguiente igualdad:

\begin{equation}
	h_i - l_i + 1 = meseta(i)
	\label{eq::def_meseta}
\end{equation}

Y tambi\'en tenemos las igualdades

\begin{align}
	h_i & = h_{l_i} \\
	l_i & = l_{h_i} \\
	\label{eq::def_indices}
\end{align}


Veamos entonces el siguiente

\begin{lemma}
	Al finalizar el ciclo, $mesetaMaxima = \max \{ meseta(i) | 0 \leq i < 
	l_n \}$ y $mesetaActual = meseta(n-1)$.
\end{lemma}

\begin{proof}
	Nuevamente demostramos todos los puntos del teorema del invariante.

	\begin{itemize}
		\item \textbf{El invariante se cumple antes de entrar al 
		ciclo:} Como $valorActual = A[0]$, en la entrada a la primera 
		iteraci\'on del ciclo se tiene efectivamente que, considerando
		que todav\'ia no hemos iterado (o sea que estamos en la 0-\'esima
		iteraci\'on).
		
		\begin{align*}
			valorActual & = A[i] = A[0] & \\
			l_0 & = \min \{ j | 0 \leq j < n, (\forall k, j \leq k \leq 0) A[k] = A[j] \} = 0 & \\
			mesetaActual & = 0 - l_0 = 1 &  \\
			mesetaMaxima & = 0 & \text{Puesto que $i = 0$}. \\
		\end{align*}
		
		\item \textbf{El invariante se mantiene entre iteraciones: }
		Supongamos entonces que al iniciar la $i$-\'esima ejecuci\'on del
		ciclo vale el invariante, con $i > 0$.
		
		La iteraci\'on del ciclo se divide en dos ramas, por lo tanto
		demostraremos cada una por separado:
		
		\begin{itemize}
			\item $A[i] = valorActual_{i-1}$. En este caso, $A[i] = A[i-1]$.
		
			Esta rama implica las siguientes asignaciones, que en concreto valen
			pues no modificamos $valorActual$ y $mesetaMaxima$,
			
			\begin{align*}
				valorActual_i & \gets valorActual_{i-1} \\
				mesetaMaxima_i & \gets mesetaMaxima_{i-1} \\
				mesetaActual_i & \gets mesetaActual_{i-1} +1 \\
			\end{align*}
		
			Los valores de $mesetaActual$,$mesetaMaxima$,$valorActual$ actualizados por esta rama
			cumplen con el invariante, ya que considerando las definiciones vemos que las asignaciones
			realizadas son correctas.
			
			\begin{align*}
				valorActual_i & = valorActual_{i-1} = A[i-1] = A[i] & \\
				l_i & = \min \{ j | 0 \leq j < n, (\forall k, j \leq k \leq i) A[k] = A[j] \} = l_{i-1} & \\ & &\text{Porque $A[i] = A[i-1]$} \\
				mesetaActual & = 1 + mesetaActual = 1 + (i-1) - l_{i-1} = i - l_{i} & \\
				h_i & = \max \{ j | 0 \leq j < n, (\forall k, j \leq k \leq i) A[k] = A[j] \} = h_{i-1} & \\ & & \text{Porque $A[i] = A[i-1]$} \\			
				mesetaMaxima_i & = mesetaMaxima_{i-1} & \\
							 & = \max \{ h_j - l_j + 1 | (\forall j, 1 \leq j < l_{i-1}) \} & \\
							 & = \max \{ h_j - l_j + 1 | (\forall j,1 \leq j<l_i) \} & \\ & & \text{Porque $l_{i} = l_{i-1}$} \\		
			\end{align*}
	
			que cumplen las condiciones enunciadas en el invariante del ciclo. Intuitivamente lo podemos ver por el hecho de que, al ser
			el valor el mismo que en la iteraci\'on anterior, seguimos en la misma meseta de tama\~no m\'aximo y por lo tanto no hay valores
			que modificar.

			\item $A[i] = valorActual$. En este caso, $A[i] \neq A[i-1]$.
		
			Esto implica que hemos terminado con la meseta que estabamos mirando y ahora comienza una nueva.
			Esto implica las asignaciones:
			
			\begin{align*}
				mesetaMaxima_i & \gets \max \{ mesetaActual_{i-1}, mesetaMaxima_{i-1} \} \\
				mesetaActual_i & \gets 1 \\
				valorActual_i & \gets A[i] \\
			\end{align*}
			
			Observemos tambi\'en que $A[i] \neq A[i-1]$ implica que $i-1 = h_{i-1}$, puesto que es el \'ultimo \'indice contiguo a
			$i-1$ tal que $A[i-1] = A[l_{i-1}]$. Tambi\'en esto implica que $i = l_i = h_{i-1}+1$.
			Veamos esto en los valores que deberiamos obtener en el teorema del invariante
			
			\begin{align*}
				valorActual_i & = A[i] \\
				l_i & = \min \{ j | 0 \leq j < n, (\forall k, j \leq k \leq i) A[k] = A[j] \} = i & \\ & & \text{Porque $A[i] \neq A[i-1]$} \\
				mesetaActual_i & = 1 = 1 + i - l_{i} = 1 + i - i = 1 & \\
				mesetaMaxima_i & = \max \{ mesetaActual_{i-1}, mesetaMaxima_{i-1} \}  & \\
							 & = \max \{ (1 + (i - 1) - l_{i-1}), \max \{ 1 + h_j - l_j | 1 \leq j < l_{i-1} \} & \\
							 & = \max \{ 1 + h_{i-1} - l_{i-1}, \max \{ 1 + h_j - l_j | 1 \leq j < l_{i-1} \} \} & \\				 
			\end{align*} 
			
			Porque $l_{i} = l_{i-1}$, $i-1 = h_{i-1}$, tenemos que
			
			\begin{align*}
				mesetaMaxima_i  & = \max \{ 1 + h_{l_{i-1}} l_{l_{i-1}},  \max \{ 1 + h_j - l_j | 1 \leq j < l_{i-1} \} \} & \\	
			\end{align*} 
			
			Y dado que $l_{i-1}=l_{l_{i-1}}$, $i-1 = h_{l_{i-1}}$, entonces
			
			\begin{align*}	 		
				mesetaMaxima_i	& = \max \{ 1 + h_j - l_j | 1 \leq j \leq l_{i-1} \} \\
								& = \max \{ 1 + h_j - l_j | 1 \leq j < l_i \}
			\end{align*}
			
			La \'ultima igualdad merece una explicaci\'on aparte. Puesto que $A[j] = A[l_{i-1}], (\forall j, l_{i-1} \leq h_{i-1}$, entonces $h_j = h_{i-1}$ y
			$l_j = l_{i-1}$. Por lo tanto,
			
			\[
				\max \{ 1 + h_j - l_j | l_{i-1} < j \leq h_{i-1} \} = 1 + h_{i-1} - l_{i-1} 
			\]   
	
			Y, como ya sabemos que $l_i = i = (i-1)+1 = h_{i-1}$, vemos que el $1 \leq j < l_{i-1}$ de la ante\'ultima igualdad anterior se puede extender a
			$1 \leq j < l_i$, porque el m\'aximo en el intervalo $[l_{i-1},h_{i-1}]$ ya lo consideramos cuando miramos el valor en $j = l_{i-1}$ 
			
			Por lo tanto para esta rama se cumple tambi\'en que vale el invariante del ciclo.
		\end{itemize}
		
		\item \textbf{Si la funci\'on variante vale cero el ciclo termina: } Si $n-i = 0$, entonces $i = n$ y se inv\'alida la guarda
		del ciclo \texttt{for}, ya que nos pasamos de rango.
		
		\item \textbf{La funci\'on variante decrece en cada iteraci\'on: } Puede verse inductivamente que $v_i = n-i$, entonces en la siguiente
		iteraci\'on tenemos que $v_{i+1} = n-i-2 < n-i-1 = v_i$.
		
		\item \textbf{El invariante y la funci\'on variante al finalizar el ciclo nos permiten demostrar la condici\'on: }
		Porque el ciclo t\'ermina luego de la $n-1$-\'esima iteraci\'on, (ya que posteriormente se invalida la guarda del ciclo),
		tenemos que las definiciones dadas nos dan:
		
		\begin{align*}
				mesetaActual_i & = (n-1)+1-l_{n-1} \\
				mesetaMaxima_i & = \max \{ h_j - l_j + 1 | (\forall j) 1 \leq j < l_{n-1} \} \\
		\end{align*}
		
		Puesto que $h_n = n-1$, porque al ser el arreglo de $n$ elementos no puede ocurrir que una meseta tenga como extremo
		derecho a un \'indice mayor que $n-1$, y $meseta(l_{n-1}) = meseta(j) \forall l_{n-1} \leq j \leq h_{n-1} = n-1$,

		\begin{align*}
				mesetaActual_i & = h_{n-1}+1-l_{n-1} = meseta(n-1) \\
				mesetaMaxima_i & = \max \{ h_j - l_j + 1 | (\forall j) 1 \leq j < l_{n-1} \} \\
		\end{align*}
		
		Como quer\'iamos ver
	\end{itemize}
	
	Como hemos demostrado todos los puntos del teorema del invariante, se cumple lo que quer\'iamos demostrar. \qed 
\end{proof}

Finalmente tenemos que

\begin{theorem}
	El algoritmo encuentra la meseta m\'axima de un arreglo $A$ de $n$ elementos.
\end{theorem}

\begin{proof}
	Por el lema anterior, al finalizar el ciclo,
	
	\begin{align*}
		mesetaMaxima & = \max \{ meseta(i) | 0 \leq i < l_{n-1} \}
		mesetaActual & = meseta(n-1)
	\end{align*}
	
	En el \'ultimo paso, volvemos a actualizar $mesetaMaxima$ con el m\'aximo entre $mesetaMaxima$ y $mesetaActual$. Por lo tanto,
	tenemos que
	
	\[
		mesetaMaxima = \max \{ meseta(n-1), \{ meseta(i) | 0 \leq i < l_{n-1} \} \}
	\]
	
	Puesto que $meseta(n-1) = meseta(l_{n-1})$ y $meseta(l_{n-1}) = meseta(j), (\forall j, l_n \leq j \leq h_n = n$, ambas
	igualdades dadas por el hecho de que el arreglo tiene $n$ elementos y por lo tanto una meseta no puede tener como \'indice del
	extremo derecho un \'indice mayor que $n-1$. Finalmente,
	
	\begin{align*}
		mesetaMaxima & = \max \{ meseta(n-1), \{ meseta(i) | 0 \leq i < l_{n-1} \} \} \\ & = \max \{ meseta(i) | 0 \leq i \leq l_{n-1} \} \\
		& = \max \{ meseta(i) | 0 \leq i \leq n-1 \}
	\end{align*}

	Como queriamos demostrar.
\end{proof}


\subsection{Complejidad de los algoritmos}

La complejidad del algoritmo, siendo $n$ y $m$ la longitud de los 
arreglos $A$ y $B$, es $O(n+m)$. Para mostrar esto, veremos que la 
complejidad de ambas partes por separado es $O(n+m)$.

Como vimos anteriormente, el algoritmo de combinaci\'on de arreglos 
ordenados realiza $n+m$ iteraciones. Esto se demuestra ya que la 
funci\'on variante dada para el algoritmo, $long(A)+long(B)$, empieza 
con valor $n+m$ y disminuye en uno en cada iteraci\'on, y cuando el 
valor de la funci\'on variante llega a 0, la guarda del ciclo se 
invalida.

La complejidad de todas las operaciones dentro del ciclo puede hacerse en 
$O(1)$ si se considera la siguiente versi\'on modificada del 
algoritmo, donde se utilizan vectores para representar las listas (lo 
cual nos permite dar la complejidad de las operaciones propuestas en 
el pseudoc\'odigo del Algoritmo~\ref{algo::merge}).

\begin{algorithm}[!h] 
	\caption{Pseudoc\'odigo para combinar dos arreglos ordenados $A$ y $B$ en un 
	arreglo ordenado $C$.}
	\label{algo::merge_posta}
	\begin{algorithmic}
		\State $i \gets 0$
		\State $j \gets 0$

		\State $n \gets long(A)$
		\State $m \gets long(B)$

		\State $C \gets crearArreglo(n+m)$
		\State $k \gets 0$
		
		\While{$i < n \vee j < m$}
			\If{$i == n$}
				\State $elem \gets B[j]$
				\State $j \gets j+1$
			\ElsIf{$empty(B)$}
				\State $elem \gets A[i]$
				\State $i \gets i+1$
			\ElsIf{$head(A) > head(B)$}
				\State $elem \gets B[j]$
				\State $j \gets j+1$
			\Else
				\State $elem \gets A[i]$
				\State $i \gets i+1$
			\EndIf
			\State $C[k] \gets elem$
			\State $k \gets k+1$
		\EndWhile
		
		\State \Return C
	\end{algorithmic}
\end{algorithm}

Como podemos ver, lo \'unico que utilizamos es la creaci\'on de un 
arreglo, cuyo tiempo de creaci\'on supondremos $O(1)$ y dado por la 
implementaci\'on interna del asignador de memoria, y por cada una de 
las $n+m$ iteraciones del ciclo principal hacemos un n\'umero 
constante de comparaciones, asignaciones 
y operaciones de suma entre enteros primitivos, lo cual supondremos bajo el modelo 
uniforme que es $O(1)$. Finalmente entonces la complejidad de esta 
parte del programa se ve f\'acilmente que es $O(n+m) + O(n+m)*O(1) = 
O(n+m)$.

De manera similar, la segunda parte del c\'odigo, donde encontramos el 
valor de la meseta m\'axima, es tambi\'en $O(n+m)$, ya que la funci\'on 
variante del ciclo, $n-i$, nos dice que hacemos $O(long(C))$ iteraciones del 
ciclo principal (siguiendo un razonamiento similar al anteriormente 
presentado), donde $C$ es el arreglo ordenado pasado por par\'ametro.

Como nosotros calculamos la longitud de la meseta del arreglo resultado del 
\textit{merge} de los arreglos originales $A$ y $B$, tenemos que 
$long(C) = n+m$ y por lo tanto el ciclo principal de esta parte del 
algoritmo hace $O(n+m)$ iteraciones. Nuevamente, dentro del ciclo 
hacemos un n\'umero finito de comparaciones, asignaciones y 
operaciones de suma entre n\'umeros enteros, que suponemos primitivos. 
Por lo tanto el costo de cada iteraci\'on es $O(1)$, y el costo 
temporal total de esta parte es $O(n+m)*O(1) = O(n+m)$.

Finalmente entonces, el costo temporal de ambas partes del algoritmo 
es $O(n+m) + O(n+m) = O(n+m)$.

La complejidad espacial tambi\'en es $O(n+m)$, ya que para separar 
ambas partes del algoritmo y simplificar la implementaci\'on, se 
decidi\'o combinar explic\'itamente los dos arreglos ordenados $A$ y 
$B$ en un nuevo arreglo ordenado $C$ y reci\'en entonces correr el 
algoritmo para encontrar la meseta m\'axima. Esto requiere entonces 
$O(n+m)$ memoria adicional para el arreglo. El resto de los algoritmos 
emplean variables locales enteras, que bajo el modelo uniForme 
supondremos requieren $O(1)$ memoria.

\subsection{Detalles de la implementaci\'on en Java}

Para representar los vectores o arreglos ordenados se utiliz\'o 
arrays est\'aticos del lenguaje (que, al ser un lenguaje 
\textit{garbage-collected}, se pueden crear de manera din\'amica, en
tiempo $O(1)$ acotado por la l\'ogica interna del asignador de memoria,
que no depende directamente de los par\'ametros de nuestro programa).

La implementaci\'on consiste en dos funciones, \textit{combinar} que 
es una implementaci\'on directa del algoritmo ~\ref{algo::merge_posta}

Tambi\'en se tiene en cuenta de que en Java, el pasaje de par\'ametros 
a funciones es siempre $O(1)$ puesto que si el tipo pasado no es 
primitivo, se pasa la referencia al mismo (que internamente se 
representa con un puntero, lo cual requiere $O(1)$ tiempo y memoria 
pasar como par\'ametro). 

Puesto que todas las otras operaciones realizadas son asignaciones, 
comparaciones o sumas de elementos del tipo \texttt{int}, que es un 
tipo primitivo en Java, la complejidad calculada anteriormente es 
v\'alida tambi\'en para la implementaci\'on en Java.

\subsection{Resultados}

\subsubsection{Correctitud - Casos de Test}

Los casos de test se crearon mediante el \textit{framework} de \textit{unit testing} para
Java, JUnit. Se busc\'o en los tests generar situaciones borde para el algoritmo, 
especificamente para estas situaciones:

\begin{itemize}
	\item Dos arreglos con una \'unica meseta para cada uno (\texttt{testResolver1}).
	\item Dos arreglos, uno de los cuales tiene longitud 1 (\texttt{testResolver4,5,6,7}).
	\item La meseta m\'as larga se encuentra completamente contenida en un arreglo (\texttt{testResolver8})
	\item La meseta m\'as larga se encuentra en la un\'on de ambos arreglos (\texttt{testResolver9})
	\item Hay m\'as de una meseta de longitud m\'axima (\texttt{testResolver2}).
	\item Todo el arreglo es la meseta de longitud m\'axima (\texttt{testResolver10}).
\end{itemize} 

M\'as otros tests creados sin un prop\'osito espec\'ifico. Dado que el algoritmo no era posible de verificar
computacionalmente sin utilizar el mismo algoritmo que programamos, los casos se verificaron a mano, dado 
que el tama\~no de los casos de test no nos pareci\'o importante para la correctitud del algoritmo (posteriormente
si fue importante para la complejidad del algoritmo).

\subsubsection{Mediciones y resultados}

Realizamos las mediciones de ejecuci\'on de dos maneras distintas: La primera utilizando para ello la funci\'on
\texttt{System.nanoSecond()}, que permite tomar mediciones de tiempo muy precisas, y la otra utilizando una variable de acumulaci\'on
dentro de los dos ciclos principales de las funciones \texttt{contarMeseta} y \texttt{combinarArreglos}.

En una primera instancia generamos una serie de arreglos al azar para mostrar que la complejidad calculada es correcta.

Para obtener los arreglos se utiliz\'o la clase de Java \texttt{Random}, para generar n\'umeros pseudoaleatorios\cite{javaapi}. La semilla del generador
de n\'umeros pseudoaleatorios se seteo en la hora actual del tiempo de test, usando para ello la llamada a sistema \texttt{System.getTimeInMillis()}.
Como la complejidad fue dada en la suma de las longitudes de los dos vectores pasados por par\'ametro, los arreglos se crearon del mismo tama\~no. Se
eligi\'o que los valores fueran al azar puesto que los valores espec\'ificos del arreglo no tienen consecuencia directa sobre la complejidad de nuestra
soluci\'on y por lo tanto nos pareci\'o lo m\'as adecuado dejar estos valores libres.

Para medir la cantidad de ejecuciones de los ciclos se agreg\'o una variable acumulador a la clase \texttt{Ejercicio1}, con el prop\'osito de que esta
sirviera para contar la cantidad de iteraciones de los ciclos realizadas. Este m\'etodo en particular ignora la cantidad de operaciones de ramas espec\'ificas
de los \texttt{ifs} y adem\'as ignora el tiempo requerido para la asignaci\'on de memoria del arreglo temporal, pero como estas operaciones se suponenen $O(1)$
no nos interesa en un primer momento para la complejidad.

El tama\~no de la muestra se eligi\'o de manera arbitraria como 50, con el prop\'osito adicional de generar instancias de tama\~no entre 1 y 100000.

Los resultados de estas mediciones se encuentran detallados en la figura~\ref{fig::ej1complejidad}. Como se esperaba, la correlaci\'on es lineal, lo
cual da resultados experimentalmente favorables a nuestra hip\'otesis de complejidad $O(long(A)+long(B))$ para los arreglos $A$ y $B$.

\begin{figure}[ht]
	\label{fig::ej1complejidad}
	\caption{Gr\'afico de la cantidad de operaciones registradas por la variable acumuladora, en funci\'on del tama\~no de la entrada.}
	\centering
	\includegraphics[width=\textwidth]{graphs/ej1complejidad.pdf}
\end{figure}

Posteriormente, se realizaron mediciones experimentales temporales, utilizando el mismo tipo de entrada (arreglos de igual tama\~no generados al azar)
pero adicionalmente se realizaron mediciones en las cuales se fij\'o el tama\~no de uno de los arreglos mientras se hizo variar al otro. 

\subsection{Conclusiones}
